Embodiments of the present invention relate to the field of road network data processing, and more specifically, relate to a method and apparatus for determining respective partition border lines in a road network.
At present, location-based services become increasingly prevalent. The connected-vehicle system as shown in FIG. 2A is a common location-based service. In a connected-vehicle system as shown in FIG. 2A, a distributed server environment is generally adopted, such that when an online location-based connected-vehicle service is provided, it can not only ensure the scalability, but also support acquisition and processing of mass-scale vehicle-carried data.
In view of the spatial characteristics of the vehicle mobility data and connected-vehicle service requests, a road network partition-based load distribution is an effective distributed policy, i.e., partitioning the entire road network into a plurality of areas (e.g., the road network data of partitions A, B, and C in FIG. 2A are deposited in servers 204A, 204B, and 204C, respectively), each server being responsible for processing data and service requests within one or more areas. In prior arts, partitioning a road network generally considers the following two factors: the first is that the loads for data processing and service processing within respective road network areas formed by partitioning should be balanced as much as possible; the second is that the occurrences of cross-partition movement of vehicles should be kept as small as possible, so as to prevent extra processing overheads for data synchronization and service switch caused by cross-partition movement of vehicles on the connected-vehicle service platform.
The connected-vehicle system as shown in FIG. 2A needs to determine which server should be assigned to process based on the location information of the mobility data and the service request. For example, a messaging gateway 201 receives location data (e.g., vehicle-carried data) of high-frequency samples from various user equipments 202 on the fly. Generally, in a road network-based partitioning manner, one partition is a set of road segments and nodes, not a geographical space defined through a spatial geometric shape, such that a physical coordinate point cannot be directly mapped to a corresponding road network partition; therefore, it cannot be directly used for data distribution decision based on the road network partitions. In view of the above, only when a border line in the spatial geometric sense is determined for each road network partition, can it be used for message distribution in the messaging gateway.
FIG. 2B shows a convex polygon method for determining a road network partition border. The black bold line 205 in the figure is a convex polygon border determined based on road network partitions included therein (FIG. 2B only shows a part of the convex polygon). It can be clearly seen from FIG. 2B that the border defined by the convex polygon will also include other road network partitions therein (see the part shown by “X” in FIG. 2B). Because road network data of different areas is generally placed in different servers, the request will constantly hop between servers.